package main

import (
	"math"
	"sort"
)

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
	mod := int(math.Pow10(9) + 7)
	abss := make([]int, len(nums1))
	sum := 0
	for i := range nums1 {
		abss[i] = abs(nums1[i] - nums2[i])
		sum += abss[i]
	}

	sort.Ints(nums1)
	diff := 0
	for i, num := range nums2 {
		if diff > abss[i] {
			continue
		}
		j := search(nums1, num)
		n, m := abss[i], abss[i]
		if j > 0 {
			n = abs(nums1[j-1] - num)
		}
		if j < len(abss) {
			m = abs(nums1[j] - num)
		}
		x := min(n, m)
		tmp := abss[i] - x
		if diff < tmp {
			diff = tmp
		}
	}
	return (sum - diff) % mod
}

func search(arr []int, tar int) int {
	left := 0
	right := len(arr)
	for left < right {
		mid := int((left + right) / 2)
		if arr[mid] < tar {
			left = mid + 1
		} else {
			right = mid
		}
	}

	return left
}

func min(x int, y int) int {
	if x > y {
		return y
	} else {
		return x
	}
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}
